import { Compare, defaultCompare, isEmpty, type ICompareFunc } from "./compare";

/**
 * ### 抽象类Heap，用于实现堆结构
 */
export abstract class Heap<T> {
  /**
   * #### 堆数组；受保护的属性，只有子类可以访问；
   */
  protected heap: T[];

  /**
   * #### 抽象属性，比较函数；需要子类去实现；
   */
  protected abstract compareFn: ICompareFunc<T>;

  // protected compFunc: ICompareFunc<T>;

  /**
   * ### 抽象类Heap构造函数
   */
  constructor() {
    // 初始化堆
    this.heap = [];
  }

  //#region 公共计算属性

  /**
   * #### 获取堆的大小
   */
  get size() {
    return this.heap.length;
  }

  /**
   * #### 判断堆是否为空
   */
  get isEmpty() {
    return this.heap.length === 0;
  }
  //#endregion

  //#region 受保护的方法

  /**
   * #### 获取左子节点的索引
   * @param index 元素索引
   * @returns
   */
  protected getLefIndex(index: number) {
    return index * 2 + 1;
  }

  /**
   * #### 获取右子节点的索引
   * @param index 元素索引
   * @returns
   */
  protected getRightIndex(index: number) {
    return index * 2 + 2;
  }

  /**
   * #### 获取父节点的索引
   * @param index 元素索引
   * @returns
   */
  protected getParentIndex(index: number) {
    if (index === 0) return void 0;
    return Math.floor((index - 1) / 2);
  }

  /**
   * #### 交换两个元素的位置
   * @param array 要交换的数组
   * @param exchangeElement 交换的元素
   * @param exchangedElement 换回的元素
   */
  protected swap(
    array: T[],
    exchangeElement: number,
    exchangedElement: number
  ) {
    [array[exchangeElement], array[exchangedElement]] = [
      array[exchangedElement],
      array[exchangeElement],
    ];
  }

  /**
   * #### 推上浮操作
   * @param index 要上浮的元素索引
   */
  protected siftUp(index: number) {
    // 获取父节点的索引
    let parent = <number>this.getParentIndex(index);
    // 当索引大于等于0且父节点的值大于当前节点的值时，交换父节点和当前节点的位置
    while (
      index >= 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) ===
        Compare.GREATER_THAN
    ) {
      this.swap(this.heap, parent, index);
      // 更新索引和父节点的索引
      index = parent;
      parent = <number>this.getParentIndex(index);
    }
  }

  /**
   * #### 推下沉操作
   * @param index 要下沉的元素索引
   */
  protected siftDown(index: number) {
    let element = index;
    const left = this.getLefIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size;
    if (
      left < size &&
      this.compareFn(this.heap[left], this.heap[element]) === Compare.LESS_THAN
    ) {
      element = left;
    }
    if (
      right < size &&
      this.compareFn(this.heap[right], this.heap[element]) === Compare.LESS_THAN
    ) {
      element = right;
    }
    if (element !== index) {
      this.swap(this.heap, element, index);
      this.siftDown(element);
    }
  }
  //#endregion

  //#region 公有的方法

  /**
   * #### 插入元素
   * @param value 插入的值
   * @returns
   */
  insert(value: T) {
    if (isEmpty(value)) return false;
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
    return true;
  }

  //   findMinimun() {
  //     return this.isEmpty ? void 0 : this.heap[0];
  //   }

  /**
   * #### 堆排序
   * @param array 要排序的数组
   */
  heapSort(array: T[]) {
    this.buildHeap(array);
    for (let i = array.length - 1; i >= 0; i--) {
      this.swap(array, i, 0);
      this.heapify(array, i, 0);
    }
  }

  /**
   * #### 获取堆数组
   * @returns 堆数组
   */
  getIsArray() {
    return this.heap;
  }

  /**
   * #### 导出推中值
   * @returns
   */
  extract() {
    if (this.isEmpty) return void 0;
    if (this.size === 1) return this.heap.shift();
    const remove = this.heap.shift();
    this.siftDown(0);
    return remove;
  }
  //#endregion

  //#region  私有方法

  /**
   * #### 交换节点，并递归的进行堆化操作
   * @param array 数组
   * @param size 数组长度
   * @param index 索引
   * @returns
   */
  // 对数组进行堆化操作
  private heapify(array: T[], size: number, index: number) {
    // 如果当前索引大于数组长度，则返回false
    if (index >= size) return false;
    // 获取当前节点的左子节点索引
    const left = this.getLefIndex(index);
    // 获取当前节点的右子节点索引
    const right = this.getRightIndex(index);
    // 将当前节点索引赋值给element
    let element = index;
    // 如果左子节点存在且左子节点大于当前节点，则将element赋值为左子节点索引
    if (
      left < size &&
      this.compareFn(array[left], array[element]) === Compare.GREATER_THAN
    ) {
      element = left;
    }
    // 如果右子节点存在且右子节点大于当前节点，则将element赋值为右子节点索引
    if (
      right < size &&
      this.compareFn(array[right], array[element]) === Compare.GREATER_THAN
    ) {
      element = right;
    }
    // 如果element不等于当前节点索引，则交换element和当前节点的值，并对element进行堆化操作
    if (element !== index) {
      this.swap(array, element, index);
      this.heapify(array, size, element);
    }
  }

  /**
   * #### 构建堆
   * @param array 数组
   */
  private buildHeap(array: T[]) {
    const last = array.length - 1;
    const lastParent = <number>this.getParentIndex(last);
    for (let i = lastParent; i >= 0; i--) {
      this.heapify(array, array.length, i);
    }
  }
  //#endregion
}
